package ZuoShen;

import java.util.ArrayList;

public class Kruskal {
    public static void main(String[] args) {
        int[][] matirx = {
                {-1, 2, 3, -1, 6},
                {2, -1, -1, 4, 2},
                {3, -1, -1, -1, -1},
                {-1, 4, -1, -1, 7},
                {6, 2, -1, 7, -1}
        };
        Graph graph = matirxToGraph(matirx);
        UnionSet unionSet = new UnionSet(new int[]{0, 1, 2, 3, 4});
        ArrayList<Edge> edges = new ArrayList<>();
        while (!Graph.edges.isEmpty()){
            Edge edge= Graph.edges.poll();
            Node from = edge.from;
            Node to = edge.to;
            if(!unionSet.isSameSet(unionSet.getNode(from.val), unionSet.getNode(to.val))){
                edges.add(edge);
                unionSet.union(unionSet.getNode(from.val), unionSet.getNode(to.val));
            }
        }
        edges.forEach((o)-> System.out.println(o.weight));

    }

    public static Graph matirxToGraph(int[][] matirx){
        Graph graph = new Graph();
        for (int i = 0; i < matirx.length; i++) {
            Node from = new Node(i);
            Graph.nodes.put(i, from);
            for (int j = 0; j < matirx.length; j++) {
                if (i != j && matirx[i][j] != -1) {
                    Node to = new Node(j);
                    Graph.nodes.put(j, to);
                    Edge edge = new Edge(from, to, matirx[i][j]);
                    Graph.edges.add(edge);
                    from.edges.add(edge);
                    from.nexts.add(to);
                }
            }
        }
        return graph;
    }
}
